1. The Field of the Invention
The field of the present invention is that of the proxy servers used in connection with accessing data over the World Wide Web ("WWW") through the Internet or other Wide Area Network ("WAN"). More particularly, the present invention involves an array of multiple proxy servers configured together to act as a single distributed cache of information identified through the use of Uniform Resource Locators ("URL"). Specifically, the invention treats intelligent or enabled clients that may directly access a desired URL data object from a particular proxy server in a proxy server array having the URL requests laterally routed or transferred amongst array members.
2. Present State of the Art
Generally speaking, the concept of a "cache" or "caching" as used in computer terminology and applications typically means making a more accessible copy of some piece of data for a performance advantage. For example, information that is cached is in many instances more accessible than it otherwise would be so that processing speed is increased since accessing the cached information is quicker.
Since having excess copies of data can create its own sort of overhead and because cache size is limited, data is not typically retained in a cache indefinitely and will eventually be overwritten after a certain amount of time if the cache is being fully utilized. This may occur according to a Leased Recently Used ("LRU") algorithm, an expiration time, or any other relevant criteria for a particular application. Caching commonly exists at the microprocessor level with instruction and data caches so as to avoid excessive accessing of system RAM and may also exist elsewhere in a computer system or in a network of computer systems.
Another form of caching is commonly used in relation to accessing data or information over the WWW. A user having Internet access can directly receive a URL identified data object, such as a web page, and then display it locally on a browser. Each time the user receives such a data object, there is a delay as the Hyper Text Transport Protocol ("HTTP") request travels across the Internet to the location identified by the URL and the destination server processing the URL request responds with the requested data object. Because the data object can be quite large, the time to access the data objects with the HTTP request and response creates a significant amount of information traveling over the Internet connection causing delays and excess overhead.
In some organizations, many of the same data objects are requested by the various users within the organization. It is therefore common to introduce a proxy server that will receive user access requests from a client application, such as a web browser. Referring to FIG. 1, the use of a proxy server acting as a cache is shown. A client application 20 will direct all URL requests to a proxy server 21 that will serve as a cache for any information (i.e., URL data objects) associated with the URL. Should the proxy server 21 not have the URL data object within its cache, it will, in turn, make access over the Internet 22 to the destination server found within the URL in order to place the data object into its cache and then respond to the client 20 URL request. Thereafter, should another client make a request to the proxy server 21, it can be serviced directly from the cache without necessary access over the Internet to the destination server found in the URL itself.
Note that the client 20 can be any software application capable of communicating or directing requests to the proxy server 21 using the HTTP protocol and would include other proxy servers, web browsers, Internet "enabled" applications, etc. Furthermore, HTTP requests contain a variety of information that can be used to "force" the proxy server 21 to access the URL data object over the Internet in order to assure that the "freshest" copy has been accessed. Such operation of proxy servers and their use as caches are generally known in the art for use in servicing HTTP requests.
It should be noted that the term URL may indicate either the address of where a data object is originally located and accessed, or the data object itself. To distinguish, a URL itself would be an address or location of the data object whereas a URL data object would be the actual web page file that is transmitted across the Internet to the client application. Though the appropriate usage is readily identifiable by context, efforts will be made throughout this application to distinguish between the two.
There are benefits of having a proxy server acting as a cache for URL data objects. One benefit is that for cached items, the total access time for a user is generally reduced since the connection between the client 20 and the proxy server 21 is typically over a Local Area Network ("LAN") rather than having to access the data object over the Internet or other Wide Area Network ("WAN"). Another benefit is for security purposes so that an organization may have a "firewall" to protect itself from unwanted outside penetration.
Larger corporations and other organizations may have many proxy servers servicing their needs. It becomes desirable in such situations to harness many proxy servers together as a single, logical distributed cache. Ideally, such a single distributed cache would have no duplication of URL data objects contained therein. Furthermore, a single distributed cache should have as little overhead as possible in servicing any given URL request that arrives at a member of the distributed cache. In other words, the actual URL data object may not be residing at the same server that originally receives the URL request and some form of forwarding, routing, or acquisition of the desired URL data object must occur in order to service that original URL request.
One attempt at creating a such a distributed cache is the Internet Cache Protocol ("ICP") that coordinates the activity of an "array" of proxy servers. Though ICP allows an array of proxy servers to function as a distributed cache, it also has some drawbacks as will be explained hereafter.
Referring now to FIG. 2, the interaction of a client with a proxy server array is shown. In such an arrangement, a client 23 will contact one of the proxy servers in the array 24 in order to access URL data objects that are available over the Internet 25. Typically, a client 23 is assigned to a particular proxy server within the proxy server array 24 and may itself be a proxy server. Since the URL data object requested by a client may exist in a different proxy server than the one contacted, a mechanism or protocol is necessary for routing the URL request from the receiving proxy server to the appropriate proxy server, or in some other way service that URL request.
Referring now to FIG. 3, proxy server array that is organized and configured according to the ICP protocol is shown. In the example shown in FIG. 3, a client 26 will direct HTTP requests to an assigned proxy server 27 that is part of an ICP proxy server array 28. Assuming that a desired URL data object is contained in the distributed cache created by the ICP proxy server array 28 and located at the proxy server 29, a scenario illustrating the operation of ICP is now shown. This scenario will also illustrate a number of problems that make ICP a less than optimal way of creating a distributed cache.
The URL request will originate at the client 26 and be received by the proxy server 27 as indicated by arrow 30. After determining that the desired URL object does not reside at the proxy server 27 in its local cache storage, a query will be sent out to all proxy servers in the ICP proxy server array 28 as indicated by the query messages path 32. In turn, every other proxy server that receives the query will give a response back to the proxy server 27 as indicated by the response message path 34. Each individual response will indicate whether or not the specified URL data object resides at that particular responding proxy server. Note that more than one of the proxy servers in the ICP proxy server array 28 may contain a given URL data object.
For purposes of this example, it is assumed that only the proxy server 29 actually contains the data object and therefore the response from proxy server 29 to proxy server 27 would be the only response having an indication that the desired or requested URL data object exists thereon. Note that for an ICP proxy server array 28 of N proxy servers, that N-1 messages were sent out by the proxy server 27 querying for the existence of the URL data object and N-1 messages were sent back to or received by the proxy server 27 in response, thus creating a fair amount of network message traffic and usage of the overall network bandwidth.
Once the proxy server 27 knows where the desired URL data object is located, it will issue a request to get the object as indicated by the get path 36. Naturally, the proxy server 29 will respond by sending the desired URL data object from the proxy server 29 to the proxy server 27 as indicated by the send object path 38. Now that the proxy server 27 has the desired URL data object, it can respond to the original URL request and return that data object to the client 26.
Cache storage redundancy can be seen since the proxy server 27 will also place the URL data object into its local cache such that the same URL data object now exists in both proxy server 27 and proxy server 29. Also, network usage overhead is significant since the total number of messages to allow the proxy server 27 the ability to service the original URL request for an ICP proxy server array 28 of N proxy servers is 2(N-1)+2 total data messages across the network.
Given the above scenario, a number of undesirable problems exhibit themselves almost immediately. First, by using a query-response scenario to contact all of the proxy servers in the ICP proxy server array, a significant amount of network resources may be consumed. Additionally, a natural consequence of the query-response scenario is that the larger the ICP proxy server array 28 becomes the greater the network overhead for each non-resident URL request, therefore adding a negative scalability component to operating an ICP server array. This means that each addition of another proxy server onto the array will in fact increase the amount of communication between the different proxy servers for all array members and for each request in order to resolve the correct location of a desired URL data object. Theoretically, there may exist an upper limit to the number of proxy servers that may be comfortably used in an ICP proxy server array 28.
Another problem is that multiple copies of the distributed cache URL data objects exist across the various proxy servers. In an extreme case, each proxy server of the ICP proxy server array 28 could become a redundant mirror of the other array members. It would be desirable to have only one copy of a URL data object existing in the entire distributed cache so that the distributed cache may be used to its full capacity.
Finally, adding or deleting proxy servers from the ICP proxy server array 28 may totally disrupt the distribution of URL data objects across the entire logical cache. In an extreme case, the distributed cache may be "emptied" upon any addition or removal of a proxy server from a proxy server array.
What is needed is a truly distributed logical cache across an array of proxy servers where a given URL data object is contained therein at only one location so as to maximize cache capacity. Furthermore, what is needed is a way to access the correct proxy server within the logical distributed cache or array of proxy servers without making a query to each and every proxy server making up the array thereby allowing a request received at one proxy server to be directly routed to the correct proxy server, or alternatively, an acquisition of the desired URL data object from the correct proxy server quickly attained. Finally, what is needed is a way of gracefully migrating cached URL data objects between the different proxy servers as a result of additions or removals of proxy servers from the proxy server array making up the distributed cache that will not require the reorientation of all URL data objects in the cache.